#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
#include <stack>
#include<iostream>
#include<sstream>
#include<deque>
#include<queue>
#include<set>
#define MOD 1000000007

class Solution
{
public:
    int minimumObstacles(std::vector<std::vector<int>>& grid)
    {
        std::vector<int> move = {-1,0,1,0,-1};
        std::deque<std::pair<int,int>> q;
        int n = grid.size();
        int m = grid[0].size();
        std::vector<std::vector<int>> dis(n, std::vector<int>(m, std::numeric_limits<int>::max()));
        q.emplace_back(0,0);
        dis[0][0] = 0;
        while (!q.empty())
        {
            auto pair = q.front();
            q.pop_front();
            if (pair.first == n-1 && pair.second == m-1)
            {
                return dis[pair.first][pair.second];
            }
            for (int i = 0;i<4;i++)
            {
                int x = pair.first + move[i];
                int y = pair.second + move[i+1];
                if (x<0||x>=n||y<0||y>=m)
                    continue;
                if (dis[x][y]<=dis[pair.first][pair.second]+grid[x][y]) continue;
                dis[x][y] = dis[pair.first][pair.second]+grid[x][y];
                if (grid[x][y]==0)
                {
                    q.emplace_front(x,y);
                }else
                {
                    q.emplace_back(x,y);
                }
            }
        }
        return -1;
    }
};
